home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 November / EnigmA AMIGA RUN 02 (1995)(G.R. Edizioni)(IT)[!][issue 1995-11][Skylink CD].iso / earcd / program / gcc / ixemul-4.lha / ixemul-41.4 / network / btree.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  18KB  |  753 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)btree.c    5.9 (Berkeley) 5/7/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  *  btree.c -- implementation of btree access method for 4.4BSD.
  43.  *
  44.  *    The design here is based on that of the btree access method used
  45.  *    in the Postgres database system at UC Berkeley.  The implementation
  46.  *    is wholly independent of the Postgres code.
  47.  *
  48.  *    This implementation supports btrees on disk (supply a filename) or
  49.  *    in memory (don't).  Public interfaces defined here are:
  50.  *
  51.  *        btree_open()    -- wrapper; returns a filled DB struct for
  52.  *                   a btree.
  53.  *
  54.  *        bt_open()    -- open a new or existing btree.
  55.  *        bt_get()    -- fetch data from a tree by key.
  56.  *        bt_seq()    -- do a sequential scan on a tree.
  57.  *        bt_put()    -- add data to a tree by key.
  58.  *        bt_delete()    -- remove data from a tree by key.
  59.  *        bt_close()    -- close a btree.
  60.  *        bt_sync()    -- force btree pages to disk (disk trees only).
  61.  */
  62.  
  63. #include <sys/param.h>
  64. #include <sys/stat.h>
  65. #include <signal.h>
  66. #include <errno.h>
  67. #include <fcntl.h>
  68. #include <db.h>
  69. #include <stdlib.h>
  70. #include <string.h>
  71. #include <unistd.h>
  72. #include "btree.h"
  73.  
  74. BTREEINFO _DefaultBTInfo = {
  75.     0,    /* flags */
  76.     0,    /* cachesize */
  77.     0,    /* psize */
  78.     strcmp,    /* compare */
  79.     0
  80. };
  81.  
  82. /*
  83.  *  BTREE_OPEN -- Wrapper routine to open a btree.
  84.  *
  85.  *    Creates and fills a DB struct, and calls the routine that actually
  86.  *    opens the btree.
  87.  *
  88.  *    Parameters:
  89.  *        f:  filename to open
  90.  *        flags:  flag bits passed to open
  91.  *        mode:  permission bits, used if O_CREAT specified
  92.  *        b:  BTREEINFO pointer
  93.  *
  94.  *    Returns:
  95.  *        Filled-in DBT on success; NULL on failure, with errno
  96.  *        set as appropriate.
  97.  *
  98.  *    Side Effects:
  99.  *        Allocates memory for the DB struct.
  100.  */
  101.  
  102. DB *
  103. btree_open(f, flags, mode, b)
  104.     const char *f;
  105.     int flags;
  106.     int mode;
  107.     const BTREEINFO *b;
  108. {
  109.     DB *db;
  110.     BTREE t;
  111.  
  112.     if ((db = (DB *) malloc((unsigned) sizeof(DB))) == (DB *) NULL)
  113.         return ((DB *) NULL);
  114.  
  115.     if ((t = bt_open(f, flags, mode, b)) == (BTREE) NULL) {
  116.         (void) free ((char *) db);
  117.         return ((DB *) NULL);
  118.     }
  119.  
  120.     db->internal = (char *) t;
  121.     db->close = bt_close;
  122.     db->del = bt_delete;
  123.     db->get = bt_get;
  124.     db->put = bt_put;
  125.     db->seq = bt_seq;
  126.     db->sync = bt_sync;
  127.     db->type = DB_BTREE;
  128.  
  129.     return (db);
  130. }
  131.  
  132. /*
  133.  *  BT_OPEN -- Open a btree.
  134.  *
  135.  *    This routine creates the correct kind (disk or in-memory) of
  136.  *    btree and initializes it as required.
  137.  *
  138.  *    Parameters:
  139.  *        f -- name of btree (NULL for in-memory btrees)
  140.  *        flags -- flags passed to open()
  141.  *        mode -- mode passed to open ()
  142.  *        b -- BTREEINFO structure, describing btree
  143.  *
  144.  *    Returns:
  145.  *        (Opaque) pointer to the btree.  On failure, returns NULL
  146.  *        with errno set as appropriate.
  147.  *
  148.  *    Side Effects:
  149.  *        Allocates memory, opens files.
  150.  */
  151.  
  152. BTREE
  153. bt_open(f, flags, mode, b)
  154.     char *f;
  155.     int flags;
  156.     int mode;
  157.     BTREEINFO *b;
  158. {
  159.     BTREE_P t;
  160.     HTABLE ht;
  161.     int nbytes;
  162.     int fd;
  163.     CURSOR *c;
  164.     BTMETA m;
  165.     struct stat buf;
  166.  
  167.     /* use the default info if none was provided */
  168.     if (b == (BTREEINFO *) NULL)
  169.         b = &_DefaultBTInfo;
  170.  
  171.     if ((t = (BTREE_P) malloc((unsigned) sizeof *t)) == (BTREE_P) NULL)
  172.         return ((BTREE) NULL);
  173.  
  174.     if (b->compare)
  175.         t->bt_compare = b->compare;
  176.     else
  177.         t->bt_compare = strcmp;
  178.  
  179.     t->bt_fname = f;
  180.     t->bt_curpage = (BTHEADER *) NULL;
  181.     t->bt_free = P_NONE;
  182.     c = &(t->bt_cursor);
  183.     c->c_pgno = P_NONE;
  184.     c->c_index = 0;
  185.     c->c_flags = (u_char) NULL;
  186.     c->c_key = (char *) NULL;
  187.     t->bt_stack = (BTSTACK *) NULL;
  188.     t->bt_flags = 0;
  189.  
  190.     /*
  191.      *  If no file name was supplied, this is an in-memory btree.
  192.      *  Otherwise, it's a disk-based btree.
  193.      */
  194.     if (f == (char *) NULL) {
  195.         /* in memory */
  196.         if ((t->bt_psize = b->psize) < MINPSIZE) {
  197.             if (t->bt_psize != 0) {
  198.                 (void) free ((char *) t);
  199.                 errno = EINVAL;
  200.                 return ((BTREE) NULL);
  201.             }
  202.             t->bt_psize = getpagesize();
  203.         }
  204.  
  205.         nbytes = HTSIZE * sizeof(HTBUCKET *);
  206.         if ((ht = (HTABLE) malloc((unsigned) nbytes))
  207.             == (HTABLE) NULL) {
  208.             (void) free((char *) t);
  209.             return ((BTREE) NULL);
  210.         }
  211.         (void) bzero((char *) ht, nbytes);
  212.         t->bt_s.bt_ht = ht;
  213.         t->bt_npages = 0;
  214.         t->bt_lorder = BYTE_ORDER;
  215.         if (!(b->flags & R_DUP))
  216.             t->bt_flags |= BTF_NODUPS;
  217.     } else {
  218.         /* on disk */
  219.         if ((fd = open(f, O_RDONLY, 0)) < 0) {
  220.             /* doesn't exist yet, be sure page is big enough */
  221.             if ((t->bt_psize = b->psize) < sizeof(BTHEADER)
  222.                 && b->psize != 0) {
  223.                 (void) free((char *) t);
  224.                 errno = EINVAL;
  225.                 return ((BTREE) NULL);
  226.             }
  227.             if (b->lorder == 0)
  228.                 b->lorder = BYTE_ORDER;
  229.  
  230.             if (b->lorder != BIG_ENDIAN
  231.                 && b->lorder != LITTLE_ENDIAN) {
  232.                 (void) free((char *) t);
  233.                 errno = EINVAL;
  234.                 return ((BTREE) NULL);
  235.             }
  236.             t->bt_lorder = b->lorder;
  237.             if (!(b->flags & R_DUP))
  238.                 t->bt_flags |= BTF_NODUPS;
  239.         } else {
  240.             /* exists, get page size from file */
  241.             if (read(fd, &m, sizeof(m)) < sizeof(m)) {
  242.                 (void) close(fd);
  243.                 (void) free((char *) t);
  244.                 errno = EINVAL;
  245.                 return ((BTREE) NULL);
  246.             }
  247.  
  248.             /* lorder always stored in host-independent format */
  249.             NTOHL(m.m_lorder);
  250.             if (m.m_lorder != BIG_ENDIAN
  251.                 && m.m_lorder != LITTLE_ENDIAN) {
  252.                 (void) free((char *) t);
  253.                 errno = EINVAL;
  254.                 return ((BTREE) NULL);
  255.             }
  256.             t->bt_lorder = m.m_lorder;
  257.  
  258.             if (t->bt_lorder != BYTE_ORDER) {
  259.                 BLSWAP(m.m_magic);
  260.                 BLSWAP(m.m_version);
  261.                 BLSWAP(m.m_psize);
  262.                 BLSWAP(m.m_free);
  263.                 BLSWAP(m.m_flags);
  264.             }
  265.  
  266.             if (m.m_magic != BTREEMAGIC
  267.                 || m.m_version != BTREEVERSION
  268.                 || m.m_psize < MINPSIZE) {
  269.                 (void) close(fd);
  270.                 (void) free((char *) t);
  271. #ifndef EFTYPE
  272. #define EFTYPE    -100
  273. #endif
  274.                 errno = EFTYPE;
  275.                 return ((BTREE) NULL);
  276.             }
  277.             t->bt_psize = m.m_psize;
  278.             t->bt_free = m.m_free;
  279.             t->bt_flags |= (m.m_flags & BTF_NODUPS) | BTF_METAOK;
  280.             (void) close(fd);
  281.         }
  282.  
  283.         /* now open the file the way the user wanted it */
  284.         if ((t->bt_s.bt_d.d_fd = open(f, flags, mode)) < 0) {
  285.             (void) free ((char *) t);
  286.             return ((BTREE) NULL);
  287.         }
  288.  
  289.         /* access method files are always close-on-exec */
  290.         if (fcntl(t->bt_s.bt_d.d_fd, F_SETFL, 1) == -1) {
  291.             (void) close(t->bt_s.bt_d.d_fd);
  292.             (void) free ((char *) t);
  293.             return ((BTREE) NULL);
  294.         }
  295.  
  296.         /* get number of pages, page size if necessary */
  297.         (void) fstat(t->bt_s.bt_d.d_fd, &buf);
  298.         if (t->bt_psize == 0)
  299.             t->bt_psize = buf.st_blksize;
  300.         t->bt_npages = (pgno_t) (buf.st_size / t->bt_psize);
  301.  
  302.         /* page zero is metadata, doesn't count */
  303.         if (t->bt_npages > 0)
  304.             --(t->bt_npages);
  305.  
  306.         if (b->cachesize == 0)
  307.             b->cachesize = DEFCACHE;
  308.  
  309.         /* get an lru buffer cache, if the user asked for one */
  310.         if ((b->cachesize / t->bt_psize) > 0) {
  311.             BTDISK *d = &(t->bt_s.bt_d);
  312.  
  313.             d->d_cache = lruinit(d->d_fd,
  314.                          (int) (b->cachesize / t->bt_psize),
  315.                          (int) t->bt_psize,
  316.                          (char *) t->bt_lorder,
  317.                          _bt_pgin, _bt_pgout);
  318.  
  319.             if (d->d_cache == (char *) NULL) {
  320.                 (void) free((char *) t);
  321.                 return ((BTREE) NULL);
  322.             }
  323.         }
  324.     }
  325.  
  326.     /* remember if tree was opened for write */
  327.     if (((flags & O_WRONLY) == O_WRONLY)
  328.         || ((flags & O_RDWR) == O_RDWR))
  329.         t->bt_flags |= BTF_ISWRITE;
  330.  
  331.     return ((BTREE) t);
  332. }
  333.  
  334. /*
  335.  *  BT_GET -- Get an entry from a btree.
  336.  *
  337.  *    Does a key lookup in the tree to find the specified key, and returns
  338.  *    the key/data pair found.
  339.  *
  340.  *    Parameters:
  341.  *        tree -- btree in which to do lookup
  342.  *        key -- key to find
  343.  *        data -- pointer to DBT in which to return data
  344.  *        flag -- ignored
  345.  *
  346.  *    Returns:
  347.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if the key is not
  348.  *        found.  If key is not found, nothing is stored in the
  349.  *        return DBT 'data'.
  350.  *
  351.  *    Side Effects:
  352.  *        None.
  353.  *
  354.  *    Warnings:
  355.  *        Return data is statically allocated, and will be overwritten
  356.  *        at the next call.
  357.  */
  358.  
  359. int
  360. bt_get(dbp, key, data, flag)
  361.     DB *dbp; 
  362.     DBT *key, *data;
  363.     u_long flag;
  364. {
  365.     BTREE_P t = (BTREE_P) (dbp->internal);
  366.     BTHEADER *h;
  367.     DATUM *d;
  368.     BTITEM *item;
  369.  
  370. #ifdef lint
  371.     flag = flag;
  372. #endif /* lint */
  373.  
  374.     /* lookup */
  375.     item = _bt_search(t, key);
  376.  
  377.     /* clear parent pointer stack */
  378.     while (_bt_pop(t) != P_NONE)
  379.         continue;
  380.  
  381.     if (item == (BTITEM *) NULL)
  382.         return (RET_ERROR);
  383.  
  384.     h = (BTHEADER *) t->bt_curpage;
  385.     data->size = 0;
  386.     data->data = (u_char *) NULL;
  387.  
  388.     /* match? */
  389.     if (VALIDITEM(t, item)
  390.         && _bt_cmp(t, key->data, item->bti_index) == 0) {
  391.         d = (DATUM *) GETDATUM(h, item->bti_index);
  392.         return (_bt_buildret(t, d, data, key));
  393.     }
  394.  
  395.     /* nope */
  396.     return (RET_SPECIAL);
  397. }
  398.  
  399. /*
  400.  *  BT_PUT -- Add an entry to a btree.
  401.  *
  402.  *    The specified (key, data) pair is added to the tree.  If the tree
  403.  *    was created for unique keys only, then duplicates will not be
  404.  *    entered.  If the requested key exists in the tree, it will be over-
  405.  *    written unless the flags parameter is R_NOOVERWRITE, in which case
  406.  *    the update will not be done.  If duplicate keys are permitted in the
  407.  *    tree, duplicates will be inserted and will not overwrite existing
  408.  *    keys.  Nodes are split as required.
  409.  *
  410.  *    Parameters:
  411.  *        tree -- btree in which to put the new entry
  412.  *        key -- key component to add
  413.  *        data -- data corresponding to key
  414.  *        flag -- R_NOOVERWRITE or zero.
  415.  *
  416.  *    Returns:
  417.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if the
  418.  *        NOOVERWRITE flag was set and the specified key exists
  419.  *        in the database.
  420.  *
  421.  *    Side Effects:
  422.  *        None.
  423.  */
  424.  
  425. int
  426. bt_put(dbp, key, data, flag)
  427.     DB *dbp;
  428.     DBT *key, *data;
  429.     u_long flag;
  430. {
  431.     BTREE_P t;
  432.     BTITEM *item;
  433.  
  434.     t = (BTREE_P)dbp->internal;
  435.  
  436.     /* look for this key in the tree */
  437.     item = _bt_search(t, key);
  438.  
  439.     /*
  440.      *  If this tree was originally created without R_DUP, then duplicate
  441.      *  keys are not allowed.  We need to check this at insertion time.
  442.      */
  443.  
  444.     if (VALIDITEM(t, item) && _bt_cmp(t, key->data, item->bti_index) == 0) {
  445.         if ((t->bt_flags & BTF_NODUPS) && flag == R_NOOVERWRITE) {
  446.             if (_bt_delone(t, item->bti_index) == RET_ERROR) {
  447.                 while (_bt_pop(t) != P_NONE)
  448.                     continue;
  449.                 return (RET_ERROR);
  450.             }
  451.         }
  452.     }
  453.  
  454.     return (_bt_insert(t, item, key, data, flag));
  455. }
  456.  
  457. /*
  458.  *  BT_DELETE -- delete a key from the tree.
  459.  *
  460.  *    Deletes all keys (and their associated data items) matching the
  461.  *    supplied key from the tree.  If the flags entry is R_CURSOR, then
  462.  *    the current item in the active scan is deleted.
  463.  *
  464.  *    Parameters:
  465.  *        tree -- btree from which to delete key
  466.  *        key -- key to delete
  467.  *        flags -- R_CURSOR or zero
  468.  *
  469.  *    Returns:
  470.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if the specified
  471.  *        key was not in the tree.
  472.  *
  473.  *    Side Effects:
  474.  *        None.
  475.  */
  476.  
  477. int
  478. bt_delete(dbp, key, flags)
  479.     DB *dbp;
  480.     DBT *key;
  481.     u_long flags;
  482. {
  483.     BTREE_P t;
  484.     BTHEADER *h;
  485.     BTITEM *item;
  486.     int ndel = 0;
  487.  
  488.     t = (BTREE_P)dbp->internal;
  489.  
  490.     if (flags == R_CURSOR)
  491.         return (_bt_crsrdel(t));
  492.  
  493.     /* find the first matching key in the tree */
  494.     item = _bt_first(t, key);
  495.     h = t->bt_curpage;
  496.  
  497.     /* don't need the descent stack for deletes */
  498.     while (_bt_pop(t) != P_NONE)
  499.         continue;
  500.  
  501.     /* delete all matching keys */
  502.     for (;;) {
  503.         while (VALIDITEM(t, item)
  504.                && (_bt_cmp(t, key->data, item->bti_index) == 0)) {
  505.             if (_bt_delone(t, item->bti_index) == RET_ERROR)
  506.                 return (RET_ERROR);
  507.             ndel++;
  508.         }
  509.  
  510.         if (VALIDITEM(t, item) || h->h_nextpg == P_NONE)
  511.             break;
  512.  
  513.         /* next page, if necessary */
  514.         do {
  515.             if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  516.                 return (RET_ERROR);
  517.             h = t->bt_curpage;
  518.         } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE);
  519.  
  520.         item->bti_pgno = h->h_pgno;
  521.         item->bti_index = 0;
  522.  
  523.         if (!VALIDITEM(t, item)
  524.             || _bt_cmp(t, key->data, item->bti_index) != 0)
  525.             break;
  526.     }
  527.  
  528.     /* flush changes to disk */
  529.     if (ISDISK(t)) {
  530.         if (h->h_flags & F_DIRTY) {
  531.             if (_bt_write(t, t->bt_curpage, NORELEASE) == RET_ERROR)
  532.                 return (RET_ERROR);
  533.         }
  534.     }
  535.  
  536.     if (ndel == 0)
  537.         return (RET_SPECIAL);
  538.  
  539.     return (RET_SUCCESS);
  540. }
  541.  
  542. /*
  543.  *  BT_SYNC -- sync the btree to disk.
  544.  *
  545.  *    Parameters:
  546.  *        tree -- btree to sync.
  547.  *
  548.  *    Returns:
  549.  *        RET_SUCCESS, RET_ERROR.
  550.  */
  551.  
  552. bt_sync(dbp)
  553.     DB *dbp;
  554. {
  555.     BTREE_P t;
  556.     BTHEADER *h;
  557.     pgno_t pgno;
  558.  
  559.     t = (BTREE_P)dbp->internal;
  560.  
  561.     /* if this is an in-memory btree, syncing is a no-op */
  562.     if (!ISDISK(t))
  563.         return (RET_SUCCESS);
  564.  
  565.     h = (BTHEADER *) t->bt_curpage;
  566.     h->h_flags &= ~F_DIRTY;
  567.  
  568.     if (ISCACHE(t)) {
  569.         pgno = t->bt_curpage->h_pgno;
  570.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  571.             return(RET_ERROR);
  572.         if (lrusync(t->bt_s.bt_d.d_cache) < RET_ERROR)
  573.             return (RET_ERROR);
  574.         if (_bt_getpage(t, pgno) == RET_ERROR)
  575.             return (RET_ERROR);
  576.     } else {
  577.         if (_bt_write(t, h, NORELEASE) == RET_ERROR)
  578.             return (RET_ERROR);
  579.     }
  580.  
  581.     return (fsync(t->bt_s.bt_d.d_fd));
  582. }
  583.  
  584. /*
  585.  *  BT_SEQ -- Sequential scan interface.
  586.  *
  587.  *    This routine supports sequential scans on the btree.  If called with
  588.  *    flags set to R_CURSOR, or if no seq scan has been initialized in the
  589.  *    current tree, we initialize the scan.  Otherwise, we advance the scan
  590.  *    and return the next item.
  591.  *
  592.  *    Scans can be either keyed or non-keyed.  Keyed scans basically have
  593.  *    a starting point somewhere in the middle of the tree.  Non-keyed
  594.  *    scans start at an endpoint.  Also, scans can be backward (descending
  595.  *    order), forward (ascending order), or no movement (keep returning
  596.  *    the same item).
  597.  *
  598.  *    Flags is checked every time we enter the routine, so the user can
  599.  *    change directions on an active scan if desired.  The key argument
  600.  *    is examined only when we initialize the scan, in order to position
  601.  *    it properly.
  602.  *
  603.  *    Items are returned via the key and data arguments passed in.
  604.  *
  605.  *    Parameters:
  606.  *        tree -- btree in which to do scan
  607.  *        key -- key, used to position scan on initialization, and
  608.  *               used to return key components to the user.
  609.  *        data -- used to return data components to the user.
  610.  *        flags -- specify R_CURSOR, R_FIRST, R_LAST, R_NEXT, or
  611.  *             R_PREV.
  612.  *
  613.  *    Returns:
  614.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if no more data
  615.  *        exists in the tree in the specified direction.
  616.  *
  617.  *    Side Effects:
  618.  *        Changes the btree's notion of the current position in the
  619.  *        scan.
  620.  *
  621.  *    Warnings:
  622.  *        The key and data items returned are static and will be
  623.  *        overwritten by the next bt_get or bt_seq.
  624.  */
  625.  
  626. int
  627. bt_seq(dbp, key, data, flags)
  628.     DB *dbp;
  629.     DBT *key, *data;
  630.     u_long flags;
  631. {
  632.     BTREE_P t;
  633.     BTHEADER *h;
  634.     DATUM *d;
  635.     int status;
  636.  
  637.     t = (BTREE_P)dbp->internal;
  638.  
  639.     /* do we need to initialize the scan? */
  640.     if (flags == R_CURSOR || flags == R_LAST || flags == R_FIRST
  641.         || !(t->bt_flags & BTF_SEQINIT)) {
  642.  
  643.         /* initialize it */
  644.         status = _bt_seqinit(t, key, flags);
  645.     } else {
  646.         /* just advance the current scan pointer */
  647.         status = _bt_seqadvance(t, flags);
  648.     }
  649.  
  650.     key->size = data->size = 0;
  651.     key->data = data->data = (u_char *) NULL;
  652.  
  653.     h = t->bt_curpage;
  654.  
  655.     /* is there a valid item at the current scan location? */
  656.     if (status == RET_SPECIAL) {
  657.         if (flags == R_NEXT) {
  658.             if (t->bt_cursor.c_index >= NEXTINDEX(h)) {
  659.                 if (NEXTINDEX(h) > 0)
  660.                     t->bt_cursor.c_index = NEXTINDEX(h) - 1;
  661.                 else
  662.                     t->bt_cursor.c_index = 0;
  663.             }
  664.         } else {
  665.             t->bt_cursor.c_index = 0;
  666.         }
  667.         return (RET_SPECIAL);
  668.     } else if (status == RET_ERROR)
  669.         return (RET_ERROR);
  670.  
  671.     /* okay, return the data */
  672.     d = (DATUM *) GETDATUM(h, t->bt_cursor.c_index);
  673.  
  674.     return (_bt_buildret(t, d, data, key));
  675. }
  676.  
  677. /*
  678.  *  BT_CLOSE -- Close a btree
  679.  *
  680.  *    Parameters:
  681.  *        tree -- tree to close
  682.  *
  683.  *    Returns:
  684.  *        RET_SUCCESS, RET_ERROR.
  685.  *
  686.  *    Side Effects:
  687.  *        Frees space occupied by the tree.
  688.  */
  689.  
  690. int
  691. bt_close(dbp)
  692.     DB *dbp;
  693. {
  694.     struct HTBUCKET *b, *sb;
  695.     BTREE_P t;
  696.     BTHEADER *h;
  697.     HTABLE ht;
  698.     int fd, i;
  699.     char *cache;
  700.  
  701.     t = (BTREE_P)dbp->internal;
  702.  
  703.     if (t->bt_cursor.c_key != (char *) NULL)
  704.         (void) free(t->bt_cursor.c_key);
  705.  
  706.     if (!ISDISK(t)) {
  707.         /* in-memory tree, release hash table memory */
  708.         ht = t->bt_s.bt_ht;
  709.         for (i = 0; i < HTSIZE; i++) {
  710.             if ((b = ht[i]) == (struct HTBUCKET *) NULL)
  711.                 break;
  712.             do {
  713.                 sb = b;
  714.                 (void) free((char *) b->ht_page);
  715.                 b = b->ht_next;
  716.                 (void) free((char *) sb);
  717.             } while (b != (struct HTBUCKET *) NULL);
  718.         }
  719.         (void) free ((char *) ht);
  720.         (void) free ((char *) t);
  721.         return (RET_SUCCESS);
  722.     }
  723.  
  724.     if ((t->bt_flags & BTF_ISWRITE) && !(t->bt_flags & BTF_METAOK)) {
  725.         if (_bt_wrtmeta(t) == RET_ERROR)
  726.             return (RET_ERROR);
  727.     }
  728.  
  729.     if (t->bt_curpage != (BTHEADER *) NULL) {
  730.         h = t->bt_curpage;
  731.         if (h->h_flags & F_DIRTY) {
  732.             if (_bt_write(t, h, RELEASE) == RET_ERROR)
  733.                 return (RET_ERROR);
  734.         } else {
  735.             if (_bt_release(t, h) == RET_ERROR)
  736.                 return (RET_ERROR);
  737.         }
  738.  
  739.         /* flush and free the cache, if there is one */
  740.         if (ISCACHE(t)) {
  741.             cache = t->bt_s.bt_d.d_cache;
  742.             if (lrusync(cache) == RET_ERROR)
  743.                 return (RET_ERROR);
  744.             lrufree(cache);
  745.         }
  746.         (void) free ((char *) h);
  747.     }
  748.  
  749.     fd = t->bt_s.bt_d.d_fd;
  750.     (void) free ((char *) t);
  751.     return (close(fd));
  752. }
  753.